/*
MIF32 TP6
ROUX Steve  10607327
XIAO Yang   10609286
*/

#include "arch.h"
#include <stdlib.h>
#include <time.h>
#include <math.h>

/* Taille de la matrice d'adjacence (matrice carrée) */
#define N 6

/* Taille de la matrice des processeurs carrée */
#define P 3

/* La valeur infinte dans la matrice */
#define _INFINITE 99

#define CHRONO_MODE

clock_t c_start, c_end;
double mpi_start, mpi_end, mpi_elapsed, c_elapsed;
int v, h;
int A[N / P][N / P], row_buf[N / P], col_buf[N / P];

/* Nombre de ligne dans la matrice*/
int MATRIX_SIZE;

/* Calcul des tailles des sous univers */
double d_sqrt_pn;
int sqrt_pn;

/* Identifiants globaux */
Coll_id cid1;
Global_id gid1,gid2,gid3,gid4;

//Compteur qui va gerer les appels de handler
class SR_count
{
	public:

		int send;

		SR_count()
		{
			send=0;
		}
	  
		void reset()
		{
			send=0;
		}
	
		void send_inc() {send++;}
		void send_dec() {send--;}		
};

SR_count Hc, Vc;
int cThread = 0;

void upon_end_of_SR_Hs(ChanAs *chan);
void upon_end_of_SR_Hr(ChanAs *chan);
void upon_end_of_SR_Vs(ChanAs *chan);
void upon_end_of_SR_Vr(ChanAs *chan);

/*Déclaration des canaux pour les communications entre processeurs*/
ChanA<int> *lr_pipe;
ChanA<int> *rl_pipe;
ChanA<int> *td_pipe;
ChanA<int> *bu_pipe;

/* definir les canaux pour les communications locaux */
//ChanL *chan[4];

ChanL * hpm2floyd;
ChanL * vpm2floyd;
ChanL * floyd2hpm;
ChanL * floyd2vpm;


/* Initialisation */
void init(int, char **)
{
	gid1.set();
	gid2.set();
	gid3.set();
	gid4.set();
	cid1.set();
}

/* Definition du graphe */
int **matrix;

/*Construction de la matrice*/
void construire_matrix()
{
	matrix = new  int*[MATRIX_SIZE];

	for(int i=0; i<MATRIX_SIZE; i++) 
	{
	matrix[i] = new  int[MATRIX_SIZE];

		for(int j=0; j<MATRIX_SIZE; j++) {
			if( (i + j)%2 ) 
			{
				/* Construction d'un graphe sous la forme d'un arbre (pas de boucle de longueur négative*/
				if (j<i)
					matrix[i][j] = _INFINITE;
				else 
					matrix[i][j] = i + j;
			}
			else {
				matrix[i][j] = _INFINITE;
				if (j==i)
					matrix[i][j] = 0;
			}
		}
	}
}

void afficher_matrix ()
{
	for(int i=0; i<MATRIX_SIZE; i++) 
	{
	fprintf(Sdf::trace,"--- matrix ->  ",Sdf::PROC_ID);
		for(int j=0; j<MATRIX_SIZE; j++) 
		{
			fprintf(Sdf::trace,"%4d",matrix[i][j]) ;
		}
	fprintf(Sdf::trace,"\n");
	fflush(Sdf::trace);
	}
fprintf(Sdf::trace,"\n");

}

/* Afficher la matrix locale avec le tag */
void afficher_matrix_locale (char tag, int tab[N/P][N/P])
{
	for(int i=0; i<N/P; i++) 
	{
		fprintf(Sdf::trace,"node %d : %c -> ",Sdf::PROC_ID,tag);
		for(int j=0; j<N/P; j++) 
		{
			fprintf(Sdf::trace,"%4d",tab[i][j]) ;
		}
	fprintf(Sdf::trace,"\n");
	}
	fflush(Sdf::trace);
}

/* Destruction de la matrice*/
void detruire_matrix() {
	
	for(int i=0; i<MATRIX_SIZE; i++) {
	
		delete[] matrix[i];
	}
	
	delete[] matrix;
	
	matrix = NULL;
}

/* copier de la colonne indice de la matrice locale dans tab */
void copy_col(int col, int tab[])
{
	for(int i=0;i<N/P;i++)
	{
		tab[i]=A[i][col];
	}
}

/* copier de la ligne indice de la matrice locale dans tab */
void copy_row(int row, int tab[])
{
	for(int i=0;i<N/P;i++)
	{
		tab[i]=A[row][i];
	}
}

/* calculer la valeur minimale */
int min( int a , int b)
{
	return ((a<b)?a:b);
}

class HpipeManager: public Thread{
	public:
		HpipeManager(): Thread((Tmf0_ptr)&HpipeManager::body){       }

		void body()
		{
			for(int k = 0; k < N ; k++){
				
				Hc.reset();
				
				if(v > k / (N / P)){

					//réception (précédent sur lr_pipe) dans col_buf;
					lr_pipe->recv(*col_buf);
					
					//attendre fin réception;
					stop();
					//émission(suivant sur lr_pipe) de col_buf, sauf si v==p-1;
					if(v!=P-1)
					{
						Hc.send_inc();
						lr_pipe->send(Sdf::STD,*col_buf, N/P);
					}

					//synchronisation avec flyod_local sur le signal hpm2flyod;
					hpm2floyd->send();

					//attendrefin d’émission;			
					if(v!=P-1)
						stop();

				}else
				if(v < k / (N / P)){
				
					//réception(précédent sur rl_pipe) dans col_buf;
					rl_pipe->recv(*col_buf);

					//attendrefin réception;
					stop();

					//émission(suivant sur rl_pipe) de col_buf, sauf si v==0;
					if(v!=0)
					{	
						Hc.send_inc();	
						rl_pipe->send(Sdf::STD,*col_buf, N/P);
					}

					//synchronisation avec flyod_local sur le signal hpm2flyod;
					hpm2floyd->send();

					//attendrefin d’émission;
					if(v!=0)
						stop();
					}
					else{ // v == k / (n / p)
					
					//copier colonne interne k % (n / p) dans col_buf;
					copy_col(k % (N / P), col_buf);


					//émission(suivant sur lr_pipe) de col_buf, sauf si v==p-1;
					if(v!=P-1)
					{
						Hc.send_inc();
						lr_pipe->send(Sdf::STD,*col_buf,N/P);
					}

					//émission(suivnat sur rl_pipe) de col_buf, sauf si v==0;
					if(v!=0)
					{
						Hc.send_inc();
						rl_pipe->send(Sdf::STD,*col_buf,N/P);
					}


					//synchronisation avec flyod_local sur le signal hpm2flyod;
					hpm2floyd->send();
			

					//attendrefins d’émission;
					if( (v!=P-1) || (v!=0) )
						stop();

				}
				
				//synchronisation avec flyod_local sur le signal flyod2hpm;
				floyd2hpm->recv();
				
			}

			if (++cThread == 3)
				Sdf::ROOT_THREAD->schedule();

		}
};

class VpipeManager: public Thread{
	public:
		VpipeManager(): Thread((Tmf0_ptr)&VpipeManager::body){       }

		void body()
		{
			for(int k = 0; k < N ; k++){
			
				Vc.reset();
				
				if(h > k / (N / P)){
					
					//réception (précédent sur td_pipe) dans row_buf;
					td_pipe->recv(*row_buf);

					//attendre fin réception;
					stop();

					//émission(suivant sur td_pipe) de row_buf, sauf si h==p-1;
					if(h!=P-1)
					{
						Vc.send_inc();
						td_pipe->send(Sdf::STD,*row_buf,N/P);
					}

					//synchronisation avec flyod_local sur le signal vpm2flyod;
					vpm2floyd->send();
			
					//attendrefin d’émission;
					if(h!=P-1)
						stop();

				}else
				if(h < k / (N / P)){

					//réception(précédent sur bu_pipe) dans row_buf;
					bu_pipe->recv(*row_buf);
			
					//attendrefin réception;
					stop();
			
					//émission(suivant sur bu_pipe) de row_buf, sauf si h==0;
					if(h!=0)
					{
						Vc.send_inc();
						bu_pipe->send(Sdf::STD,*row_buf,N/P);
					}

					//synchronisation avec flyod_local sur le signal vpm2flyod;
					vpm2floyd->send();
			
					//attendrefin d’émission;
					if(h!=0)
						stop();

				}else{ // h == k / (n / p)
				
					//copier ligne interne k % (n / p) dans row_buf;
					copy_row(k % (N / P), row_buf);
			
					//émission(suivant sur td_pipe) de row_buf, sauf si h==p-1;
					if(h!=P-1)
					{
						Vc.send_inc();
						td_pipe->send(Sdf::STD,*row_buf,N/P);
					}

					//émission(suivnat sur bu_pipe) de row_buf, sauf si h==0;
					if(h!=0)
					{
						Vc.send_inc();
						bu_pipe->send(Sdf::STD,*row_buf,N/P);
					}

					//synchronisation avec flyod_local sur le signal vpm2flyod;
					vpm2floyd->send();
			
					//attendrefins d’émission;
					if ( (h!=P-1) || (h!=0) )
						stop();
				}
				
				//synchronisation avec flyod_local sur le signal flyod2vpm;
				floyd2vpm->recv();

			}

			if (++cThread == 3)
				Sdf::ROOT_THREAD->schedule();

		}
};

class FloydLocal: public Thread{
	public:
		FloydLocal(): Thread((Tmf0_ptr)&FloydLocal::body){}

		void body()
		{
			for(int k = 0; k < N; k++){
			
				//réception synchronedu signal hpm2flyod;
				hpm2floyd->recv();
				
				//réception synchronedu signal vpm2flyod;
				vpm2floyd->recv();
				
				//mise à jour locale de A selon la procédure de Floyd;
				for(int i = 0; i < (N / P) ; i ++)
					for(int j = 0; j < (N / P) ; j ++)
						A[i][j] = min(A[i][j], row_buf[j] + col_buf[i]);

				//émission synchronedu signal flyod2hpm;
				floyd2hpm->send();

				//émission synchronedu signal flyod2vpm;
				floyd2vpm->send();

			}

			if (++cThread == 3)
				Sdf::ROOT_THREAD->schedule();

		}
};

HpipeManager *h_pipe_manager;
VpipeManager *v_pipe_manager;
FloydLocal *floyd_local;

/* Classe principale */
class Root_thread: public Thread{

private:

	int proc_id;

public:

	Root_thread(): Thread((Tmf0_ptr)&Root_thread::body) {}

	~Root_thread() {}

	void body()
	{
		if (Verif())
			{
				#ifdef CHRONO_MODE
				/* Lancement de la mesure */
				c_start = clock();
				mpi_start = MPI_Wtime();
				#endif
	
				proc_id = Sdf::PROC_ID;
				sqrt_pn = P;
				MATRIX_SIZE= N;
	
				/* Calcul des positions v et h de chaque processeur dans la matrice des processeurs*/
				h = proc_id/sqrt_pn;
				v = proc_id%sqrt_pn;
	
				/* Chaque processus construit la meme matrice */
				construire_matrix();

				if(proc_id==0)
				{
					#ifdef CHRONO_MODE		
					fprintf(Sdf::trace,"--- CHRONO_MODE ---\n",Sdf::PROC_ID);
					#endif
					#ifndef CHRONO_MODE		
					fprintf(Sdf::trace,"--- NORMAL_MODE ---\n",Sdf::PROC_ID);
					afficher_matrix();
					#endif
				}

				/* Répartition des éléments de la matrice + initialisation de C */
				for (int i=0; i < N/P; i++ )
				{
					for(int j=0; j<N/P; j++)
					{
						A[i][j] = matrix[((h*(N/P))+i)][((v*(N/P))+j)];
					} 
				}

				#ifndef CHRONO_MODE
				fprintf(Sdf::trace,"\n\nnode %d --- Début de l'algorithme\n",proc_id);
				afficher_matrix_locale('D',A);
				fflush(Sdf::trace);
				#endif

				hpm2floyd = new ChanL ();
				floyd2hpm = new ChanL ();
				floyd2vpm = new ChanL ();
				vpm2floyd = new ChanL ();

				floyd_local = new FloydLocal();
				h_pipe_manager 	= new HpipeManager();
				v_pipe_manager = new VpipeManager();

				Thread *proc_tabl[3] = {floyd_local, h_pipe_manager, v_pipe_manager};
				int pri[3] = {1, 1, 1};

				floyd_local->setup(0);
				h_pipe_manager->setup(0);
				v_pipe_manager->setup(0);

				/* left to right */
				int right_id = ((proc_id % P < P - 1)? proc_id + 1 : Sdf::NOPID);
				lr_pipe = new ChanA<int>(gid1,right_id,N/P);
	
				/* right to left */
				int left_id = ((proc_id % P > 0)? proc_id-1 : Sdf::NOPID);
				rl_pipe = new ChanA<int>(gid2,left_id,N/P);
	
				/* top to down */
				int bottom_id = ((proc_id < Sdf::PROC_NB - P)? proc_id + P : Sdf::NOPID);
				td_pipe = new ChanA<int>(gid3,bottom_id,N/P);
	
				/* bottom to up */
				int top_id = ((proc_id > P-1)? proc_id - P : Sdf::NOPID);
				bu_pipe = new ChanA<int>(gid4,top_id,N/P);
	
				lr_pipe->set(Sdf::SND, upon_end_of_SR_Hs, &Hc);
				lr_pipe->set(Sdf::RCV, upon_end_of_SR_Hr, &Hc);
				rl_pipe->set(Sdf::SND, upon_end_of_SR_Hs, &Hc);
				rl_pipe->set(Sdf::RCV, upon_end_of_SR_Hr, &Hc);
	
				td_pipe->set(Sdf::SND, upon_end_of_SR_Vs, &Vc);
				td_pipe->set(Sdf::RCV, upon_end_of_SR_Vr, &Vc);
				bu_pipe->set(Sdf::SND, upon_end_of_SR_Vs, &Vc);
				bu_pipe->set(Sdf::RCV, upon_end_of_SR_Vr, &Vc);
	
				floyd_local->schedule();
				h_pipe_manager->schedule();
				v_pipe_manager->schedule();

				//synchronous
				/*Attendre fin d'émission et de reception*/	
				stop();
	
				#ifndef CHRONO_MODE		
				fprintf(Sdf::trace,"node %d --- Fin de l'algorithme\n",proc_id);
				afficher_matrix_locale('F',A);
				fflush(Sdf::trace);
				#endif
	
				#ifdef CHRONO_MODE 
				/* Arret de la mesure */
				c_end = clock();	
				mpi_end = MPI_Wtime();		
				c_elapsed = ((double)c_end - c_start) / CLOCKS_PER_SEC;	/* Conversion en seconde */
				mpi_elapsed = mpi_end - mpi_start;	
				fprintf(Sdf::trace,"Temps d'execution sur proc %d: c:%4.4f, mpi:%4.4f ( nb sommets:%d, nb proc:%d ) \n",Sdf::PROC_ID,c_elapsed,mpi_elapsed,MATRIX_SIZE,Sdf::PROC_NB);
				fflush(Sdf::trace);		
				#endif

				/*Destructions*/
				detruire_matrix();
				delete hpm2floyd;
				delete floyd2hpm;
				delete floyd2vpm;
				delete vpm2floyd;
				delete floyd_local;
				delete h_pipe_manager;
				delete v_pipe_manager;
		}
	}

protected :

		/* Test des contraintes d'intégrités liés a la parallélisation de l'algorithme*/
		int Verif()
		{
			if (Sdf::PROC_NB!=P*P)
			{
				if (Sdf::PROC_ID==0)
				{
					fprintf(Sdf::trace,"! Nombre de processeur incorrect \n",Sdf::PROC_ID);
					fflush(Sdf::trace);
				}
				return 0;
			}
			if (N<P)
			{ 
				if (Sdf::PROC_ID==0)
				{
					fprintf(Sdf::trace,"! Nombre de données N insufisante \n",Sdf::PROC_ID);
					fflush(Sdf::trace);
				}
				return 0;
			}
			if (N%P!=0)
			{
				if (Sdf::PROC_ID==0)
				{
					fprintf(Sdf::trace,"! Division de N/P non entiere \n",Sdf::PROC_ID);
					fflush(Sdf::trace);
				}
				return 0;
			}
			return 1;
		}
};

//gestion des handlers

void upon_end_of_SR_Hs(ChanAs *chan)
{
	((SR_count *)(chan->get_hndlr_data_ptr(Sdf::SND)))->send_dec();

	if((((SR_count *)(chan->get_hndlr_data_ptr(Sdf::SND)))->send == 0))
		h_pipe_manager->schedule();
}

void upon_end_of_SR_Hr(ChanAs *chan)
{
	h_pipe_manager->schedule();
}

void upon_end_of_SR_Vs(ChanAs *chan)
{
	((SR_count *)(chan->get_hndlr_data_ptr(Sdf::SND)))->send_dec();

	if((((SR_count *)(chan->get_hndlr_data_ptr(Sdf::SND)))->send == 0))
		v_pipe_manager->schedule();
}

void upon_end_of_SR_Vr(ChanAs *chan)
{
	v_pipe_manager->schedule();
}

MAIN(Root_thread, init, Sdf::empty_f, Sdf::empty_e)
